\chapter{Trabalho Anterior e Tecnologias Utilizadas}

Neste capítulo conheceremos com mais detalhes o trabalho no qual este se baseia, de forma a entender a idéia original na qual foi baseada o protótipo construído. As tecnologias utilizadas serão estudadas em detalhes para que possamos compreender onde e como cada uma delas foi utilizada nos diferentes processos envolvidos na realização do concurso.

\section{Trabalho de referência}
\label{trabalhoReferencia}

O protótipo desenvolvido neste trabalho se baseia na idéia inicial concebida por um outro trabalho \cite{LPS}. Desta forma, precisamos conhecer esta idéia inicial antes de prosseguirmos com o entendimento do protótipo.

O projeto anterior previa a criação de dois módulos, o Módulo Coletor e o Módulo de Autenticação. A concepção original destes módulos será detalhada nas seções \ref{moduloColetorOriginal} e \ref{moduloAutenticadorOriginal}.

\subsection{Módulo Coletor}
\label{moduloColetorOriginal}

O módulo coletor foi idealizado para atuar na primeira etapa do processo descrito na seção \ref{processo}, quando o candidato comparece ao local determinado para a realização da prova. Este módulo é responsável pela automatização da coleta da impressão digital do candidato, pela obtenção do número de inscrição e pela geração e impressão de uma etiqueta contendo um código de barras bidimensional com essas duas informações. O caso de uso deste módulo se encontra ilustrado na figura \ref{figuraUsecaseColetorOriginal}.

\begin{figure}[h]
   \begin{center}
     \scalebox{0.75}{\includegraphics{imagens/usecaseColetorOriginal.jpg}}
   \end{center}
   \caption{Caso de uso do módulo coletor segundo projeto original \cite[p.82]{LPS}\label{figuraUsecaseColetorOriginal}}
\end{figure}

A primeira tarefa a ser realizada por este módulo é a coleta da impressão digital. Essa coleta precisa ser realizada várias vezes para que possa ser escolhida a melhor amostra. Após realizada esta tarefa o sistema já possui a primeira das informações que serão gravadas na etiqueta.

Depois de coletadas as digitais, o sistema então realiza a leitura do código de inscrição do candidato, que se localiza na região do cartão resposta marcada com a letra B na figura \ref{figuraCartaoRespostaAreas}. Para detectar o número de inscrição corretamente, o sistema deve fotografar uma sequência de imagens com um determinado intervalo e utilizar em cada amostra técnicas de processamento de imagens. Cada imagem é processada e o resultado comparado com as duas imagens anteriores e caso as três últimas imagens consecutivas obtenham a mesma leitura então esta é considerada correta. 

De posse do número de inscrição e da melhor amostra da digital do candidato, o sistema gera um código de barras bidimensional contendo essas duas informações e permite a impressão do mesmo em uma etiqueta adesiva, que deve ser colada no cartão resposta na região marcada com a letra A na figura \ref{figuraCartaoRespostaAreas}.

\begin{figure}[h]
   \begin{center}
     \scalebox{0.7}{\includegraphics{imagens/cartaoRespostaAreas.jpg}}
   \end{center}
   \caption{Cartão resposta utilizado pelo NCE, separado por áreas\label{figuraCartaoRespostaAreas}}
\end{figure}

Após todas as etapas do módulo coletor terem sido completadas com sucesso, temos armazenada no cartão resposta a impressão digital do indivíduo que realizou a prova. Essa informação pode ser recuperada a qualquer tempo, permitindo que a identidade do candidato que possivelmente assumirá a vaga no futuro seja comparada com a identidade do indivíduo que realizou a prova. Essa tarefa será realizada pelo módulo de autenticação num segundo momento.

\subsection{Módulo de Autenticação}
\label{moduloAutenticadorOriginal}

O módulo de autenticação tem como objetivo atuar na segunda etapa do processo descrito na seção \ref{processo}, quando temos a admissão de um candidado que foi aprovado no concurso em questão. Este módulo precisa coletar as digitais do indivíduo que está comparecendo para assumir o cargo, ler a etiqueta impressa no cartão resposta deste candidato e verificar se este é o mesmo indivíduo que realizou a prova num primeiro instante.

\begin{figure}[h]
   \begin{center}
     \scalebox{0.85}{\includegraphics{imagens/usecaseAutenticadorOriginal.jpg}}
   \end{center}
   \caption{Caso de uso do módulo de autenticação segundo projeto original \cite[p.83]{LPS}\label{figuraAutenticadorColetorOriginal}}
\end{figure}

Primeiramente é preciso coletar a digital do candidato. Mais uma vez serão coletadas três amostras para que possa ser escolhido a melhor. Depois de obtida esta impressão digital, o sistema já possui o primeiro dos elementos para fazer a verificação a que se propõe.

A próxima etapa a ser realizada é a decodificação da impressão digital contida na etiqueta, que foi gerada pelo módulo coletor. Para tal, é preciso que uma câmera capture uma imagem nítida do código de barras bidimensional, que será decodifcado. Esse processo nos fornece a impressão digital e o número de inscrição do candidato no momento da realização da prova, contribuindo com o elemento restante para a conferência das digitais.

De posse da impressão digital coletada nas duas etapas do processo -- a impressão digital do indivíduo que realizou a prova anteriormente e a outra impressão digital do indivíduo que está agora assumindo o cargo --, o módulo de autenticação pode realizar a comparação e dizer se pertencem ou não ao mesmo indivíduo. Caso o sistema acuse diferença nas impressões digitais, então é constatada a fraude e o processo de admissão é abortado. Caso contrário, então o processo segue normalmente.

\section{Tecnologias Utilizadas}

Para que fosse possível a concepção desse sistema, foi realizada no trabalho anterior uma extensa pesquisa sobre biometria e impressões digitais eletrônicas, processamento de imagens e códigos de barra bidimensionais. Então, antes de detalhar a integração dessas tecnologias e construção do protótipo, vamos fazer uma análise isolada de cada tecnologia para que então possamos ver como foram usadas dentro do protótipo.

\subsection{Impressão digital}
\label{tecnologiaImpressaoDigital}

Dentre os diversos métodos de biometria, o uso de impressões digitais é o mais adequado para esse sistema, pois consegue uma boa pontuação em todos os quesitos que qualificam um método biométrico, além de ser um método de baixo custo \cite[s. 2.1]{LPS}.

Para entender como podemos identificar unicamente um ser humano através de suas impressões digitais, é preciso entender o que elas possuem de tão peculiar. 

A pele, na região da ponta dos dedos, tem em sua superfície cristas e vales que compõem uma espécie de relevo, formando o que chamamos de dermatóglifos -- do grego \textit{derma}, que significa pele, e \textit{glifo}, que significa inscrição --. Essa superfície se forma até o sétimo mês da gestação, momento a partir do qual não se modifica mais. Nesse processo de formação, temos a influência não somente do código genético, mas também pelo microambiente, o que faz com que mesmo gêmeos de código genético idêntico tenham dermatóglifos distintos \apud[p. 7]{RICHARDS}{CESAR}. Desta forma podemos dizer que esta se trata de uma característica imutável durante toda a vida do indivíduo, exceto em casos onde haja algum acidente que acarrete alguma transformação. 

\subsubsection{Minúcias e Singularidades}

Se projetarmos os dermatóglifos em uma superfície plana, formamos uma imagem que conhecemos como impressão digital. Nessa imagem, chamamos então de minúcias os pontos notáveis que se diferenciam, de alguma forma, da maioria da área da digital. Essas minúcias podem ser classificadas conforme a figura \ref{figuraMinucias}.

\begin{figure}[h]
   \begin{center}
     \scalebox{1.6}{\includegraphics{imagens/minucias.png}}
   \end{center}
\centering\scriptsize
\begin{tabular}{|l|l|}
\hline
(a)	& Extremidade (\textit{Termination})\\
(b)	& Bifurcação (\textit{Bifurcation})\\
(c)	& Inclusão (\textit{Lake})\\
(d)	& Ilha (\textit{Island})\\
(e)	& Crista Independente (\textit{Independent Ridge})\\
(f)	& Espora (\textit{Spur})\\
(g)	& Cruzamento (\textit{Bridge})\\
\hline
\end{tabular}
   \caption{Tipos de minúcias. Adaptado de \cite{BRAGGINS}\label{figuraMinucias}}
\end{figure}

Em uma impressão digital, existem dezenas dessas peculiaridades, o que diminui drasticamente as chances de dois indivíduos distintos possuirem o mesmo conjunto de minúcias em suas impressões digitais. Numa boa imagem, podem ser encontradas de 40 a 100 minúcias, sendo que apenas 12 destas já seriam suficientes para identificar uma pessoa com grau de confiabilidade da ordem de $10^{-12}$ \apud[p. 31]{HONGJAIN}{LPS}.

Além das minúcias, é considerado ainda o aspecto geral da imagem da impressão digital, conhecido como singularidade. As principais singularidades estão descritas na figura \ref{figuraSingularidades}. Essa classificação visa separar as impressões digitais em classes, de forma a diminuir o espaço de busca quando precisamos verificar se uma determinada digital se encontra em um banco de dados. Dessa forma, podemos fazer as comparações de minúcias somente nas digitais que possuem a mesma classe, evitando que toda a base de dados seja verificada.

\begin{figure}[h]
   \begin{center}
     \scalebox{0.6}{\includegraphics{imagens/singularidades.png}}
   \end{center}
\centering\scriptsize
\begin{tabular}{|l|l|l|}
\hline
(a)	& Arco angular (\textit{Tentarch}) & 7,8\% \\
(b)	& Arco plano (\textit{Arch}) & 6,2\% \\
(c)	& Presilha externa (\textit{Right loop}) & 36,5\% \\
(d)	& Presilha interna (\textit{Left Loop}) &  17\% \\
(e)	& Vertículo (\textit{Whorl}) & 32,5\% \\
\hline
\end{tabular}
   \caption{Tipos de singularidades e frequências na população. Adaptado de \cite{BRAGGINS}\label{figuraSingularidades}}
\end{figure}

\subsubsection{\textit{Templates}}

Embora as minúcias e singularidades possam ser facilmente identificadas numa análise feita por seres humanos, não é tão trivial representá-las de forma a tornar possível o seu processamento por sistemas computacionais. É preciso guardar todos os dados observados de forma organizada, permitindo que todos os detalhes relevantes possam ser armazenados e resgatados no futuro. São utilizados então os \textit{templates}, que são um conjunto de \textit{bytes} dispostos de tal forma a armazenar todas as informações encontradas em uma amostra de impressão digital. 

Diversas instituições criaram seus padrões para os \textit{templates}. Cada uma dessas instituições utiliza um certo conjunto de minúcias, bem como uma certa organização para descrever a singularidade da digital e o tipo, localização e orientação de cada uma das minúcias. Além dos diversos padrões proprietários desenvolvidos pelas empresas com pesquisas na área de biometria, temos dois padrões internacionais para \textit{templates} de digitais: o ISO 19794-2 \cite{ISO19794-2} e o ANSI 378-2004 \cite{ANSI378}. O objetivo principal destes padrões é promover a interoperabilidade entre diversos dispositivos que manipulam bancos de dados de impressões digitais, permitindo, por exemplo, que um \textit{template} extraído por um determinado dispositivo possa ser utilizado por um outro dispositivo que utilize o mesmo padrão.

Como podem ser encontradas diferentes quantidades de mínucias nas diversas digitais, os \textit{templates} tem tamanho variável. O tamanho do \textit{template} também determina sua confiabilidade relativa, pois em uma imagem de boa qualidade podem ser identificadas mais minúcias, o que nos dará um \textit{template} relativamente maior e mais confiável. Já em uma imagem de baixa qualidade teremos um template menor e menos confiável.

\subsubsection{\textit{Enrolling}}

Quando desejamos armazenar uma impressão digital para que possam ser feitas verificações futuras, é arriscado extrairmos apenas uma amostra da digital e confiar na mesma. Como acabamos de ver, uma amostra pode gerar uma imagem de baixa qualidade, o que nos dará um template pobre, pouco confiável.

O processo de \textit{enrolling} tem como objetivo a obtenção de um \textit{template} muito confiável de uma impressão digital. Para isso, nesse processo são obtidas várias amostras de uma mesma impressão digital. Cada uma dessas amostras é primeiramente validada, sendo descartada caso não seja atingido o número mínimo de minúcias necessárias para sua utilização. Depois de obtidas as várias amostras necessárias, elas são então consolidadas formando um \textit{template} que contém informações de todas as amostras. Essa consolidação é feita observando-se as minúcias que aparecem em mais de uma amostra, excluindo assim potenciais falsas minúcias obtidas por causa de falhas no processo de extração do \textit{template}. O número de amostras necessárias vai variar conforme a confiabilidade desejada, mas geralmente está entre três e cinco amostras.

\subsubsection{\textit{Matching}}

De posse de dois \textit{templates} de duas extrações diferentes, é fundamental conseguirmos saber se eles pertencem a mesma digital e, consequentemente, ao mesmo indivíduo. A este processo de comparação dá-se o nome de \textit{matching}. 

O \textit{matching} consiste em pegar dois \textit{templates} e verificar se ambos pertencem a mesma digital. Para isso, primeiramente é preciso conferir a singularidade. Se pertencerem ao mesmo grupo, então comparamos as minúcias, sendo requerido que um determinado número de minúcias seja encontrado em ambos os \textit{templates}. Este número geralmente é parametrizável e reflete diretamente a confiabilidade da resposta dada na comparação. No entanto um número muito alto pode acusar como diferentes duas digitais na verdade iguais -- devido a imperfeições na imagem de uma das capturas, etc --, o que também não é desejável. Essa parametrização é feita de acordo com o propósito do \textit{matching}, não havendo um número predeterminado de minúcias a serem encontradas em ambos os \textit{templates}.

Para realização do \textit{matching}, é necessário que os \textit{templates} estejam no mesmo padrão. No entanto, se conhecendo dois ou mais padrões, geralmente é possível realizar a conversão. A maioria das APIs disponibiliza esta função de conversão de \textit{templates}.

\pagebreak

\subsection{Processamento de imagens}
\label{tecnologiaProcessamentoImagem}

Além de todo o aparato de processamento de imagens que está embutido no processo de identificação das minúcias das impressões digitais, este projeto precisa utilizar processamento de imagens para reconhecer o número de inscrição preenchido pelo candidato através de uma fotografia tirada no momento da realização da prova, conforme descrito na seção \ref{moduloColetorOriginal}. Para tal, técnicas de processamento de imagens precisam ser aplicadas à foto do cartão resposta para identificar o número que se encontra na área B da figura \ref{figuraCartaoRespostaAreas}.

Com este objetivo, foi desenvolvida no trabalho anterior uma aplicação em Matlab que recebe como entrada uma imagem com o cartão resposta e retorna o número de inscrição contido no mesmo. Esta aplicação faz a identificação do número de inscrição de uma imagem já previamente gravada em arquivo no computador e exibe o número de inscrição encontrado, não tendo sido desenvolvida nenhum tipo de integração com a câmera digital ou qualquer outro dispositivo.

Como a utilização desta aplicação de reconhecimento do número de inscrição não requer o conhecimento de nenhum termo específico referente as técnicas de processamento de imagens utilizadas nem sofrerá nenhum tipo de ajuste nesse projeto, nos limitaremos a explicar como ela foi integrada ao restante do protótipo na seção \ref{prototipo}. Mais detalhes sobre as técnicas utilizadas podem ser encontrados no trabalho anterior \cite[p.36]{LPS}.

\subsection{Código de barras bidmensional}
\label{tecnologiaCodigoBarras}

Como não será utilizado um banco de dados para que as impressões digitais obtidas pelo módulo coletor sejam posteriomente conferidas pelo módulo de autenticação, foi então estabelecido que essas digitais seriam armazenadas numa etiqueta colada no próprio cartão resposta do candidato. Para que isso fosse possível, foram feitas no trabalho anterior pesquisas sobre um código de barras bidimensional conhecido como QRCode.

O QRCode -- Quick Response Code --, mostrado na figura \ref{figuraQRCode}, foi criado por uma empresa japonesa chamada Denso Wave em 1994 com o intuito de ser um código com alto poder de armazenamento, compacto, de leitura fácil e rápida. Em 2000 foi aprovado como o padrão internacional ISO-18004 \cite{ISO18004}. 

\begin{figure}[h]
   \begin{center}
     \scalebox{0.8}{\includegraphics{imagens/qrcode.png}}
   \end{center}
   \caption{QRCode.\label{figuraQRCode}}
\end{figure}

\subsubsection{Propriedades}

Uma característica do QRCode muito importante para este trabalho é a resistência a rotação, que permite a leitura do código estando este posicionado em qualquer angulação. Como o leitor será uma câmera digital manipulada por um ser humano, seria impossível fazer a leitura de forma totalmente alinhada. A figura \ref{figuraQRCodeRotacionado} mostra como é realizada a leitura em caso de rotações.

\begin{figure}[h]
   \begin{center}
     \scalebox{0.8}{\includegraphics{imagens/qrcode-rotacionado.png}}
   \end{center}
   \caption{QRCode rotacionado. Os \textit{Find Patterns}, localizados em 3 dos cantos do símbolo, são utilizados para detectar a rotação e possibilitar a leitura em qualquer angulação.\label{figuraQRCodeRotacionado}}
\end{figure}

Há também nesta tecnologia a capacidade de correção de erros, que recupera os dados existentes em regiões eventualmente danificadas. Isso também é crucial para este projeto, pois o cartão resposta ficará um longo tempo exposto durante a realização da prova, sendo manipulado em vários momentos, o que pode causar algum desgaste no mesmo. Podem ser escolhidos 4 níveis de correção, conforme a tabela \ref{tabelaQRCodeCorrecaoErro}

\begin{table}[h]
\caption{Níveis de correção de erro suportados pelo QRCode\label{tabelaQRCodeCorrecaoErro}} 
\center{
\begin{tabular}{l|l}
\hline
Nível   & \% falha tolerado\\
\hline
L                 & 7\% \\
M                 & 15\% \\
Q                 & 25\% \\
H                 & 30\% \\
\hline
\end{tabular}}
\end{table}

A correção de erro é implementada utilizando-se um algoritmo chamado \textit{Reed-Solomon}. Este algoritmo requer que alguns dados sejam duplicados para que possam ser recuperados em caso de perda. Dessa forma, quanto maior o nível de correção de erro, menor será o espaço destinado para os dados para uma mesma versão do QRCode (versões serão explicadas um pouco a frente). Uma tabela completa pode ser vista no apêndice \ref{qrcodeTabelaVersoes}.

O QRCode também possui outra propriedade interessante: É possível a leitura de um código mesmo se este estiver distorcido, geralmente por decorrência de um posicionamento inclinado diante do leitor ou alguma deformação ótica causada pela lente usada para leitura. Isso aumenta bastante o sucesso em operações de leitura, principalmente em situações como a desse projeto, onde o código se encontra impresso em uma superfície maleável como o papel do cartão resposta. A figura \ref{figuraQRCodeDeformado} mostra dois tipos de deformação toleráveis pelo algoritmo de leitura.

\begin{figure}[h]
   \begin{center}
     \scalebox{0.8}{\includegraphics{imagens/qrcode-deformado.png}}
   \end{center}
   \caption{Exemplos de deformações que o leitor de QRCode consegue processar.\label{figuraQRCodeDeformado}}
\end{figure}

\subsubsection{Estrutura}

Todas essas propriedades do QRCode são possíveis pois o símbolo gerado possui toda uma estrutura que as viabiliza. Podemos notar na figura \ref{figuraQRCodeEstrutura} que diversos padrões auxiliares são utilizados para que o algoritmo possa ter tais habilidades.

\begin{figure}[h]
   \begin{center}
     \scalebox{0.8}{\includegraphics{imagens/qrcode-estrutura.jpg}}
   \end{center}
   \caption{Estrutura de um símbolo QRCode.\label{figuraQRCodeEstrutura}}
\end{figure}

\begin{itemize}
\item \textit{Finder Pattern} - Esta marcação se encontra em três dos quatro cantos e é a principal das marcações. Através dela o leitor pode detectar a posição, o tamanho e o ângulo do símbolo 
\item \textit{Timing Pattern} - Padrão utilizado para que o leitor possa encontrar o ponto central de cada célula. Consiste de células alternadamente pretas e brancas, que possibilitam ao leitor determinar o espaçamento de uma célula para a outra. Também é importante no caso de distorções.
\item \textit{Alignment Pattern} - Esta marcação é utilizada para corrigir distorções no símbolo, tornando possível fazer uma projeção correta  a partir dos pontos centrais dos \textit{alignment patterns} detectados na imagem.  
\item \textit{Quiet Zone} - Consiste em uma margem ao redor do símbolo, que deve ser de no mínimo 4 células de largura. Esta área é necessária  para que eventuais impressões ao redor do símbolo não interfiram na leitura do mesmo.
\item \textit{Cells} - Também chamadas de módulos, são as regiões destinadas ao armazenamento dos dados que estão sendo codificados. Todas as células não pertencentes aos marcadores descritos anteriormente compõem a área de dados. Cada célula pode assumir o valor preto ou branco.
\end{itemize}

Existem diversas variações desta estrutura básica, chamadas de versões. Todas as versões possuem basicamente a mesma estrutura, mas o número de \textit{alignment patterns}, por exemplo, vai variar conforme o tamanho. As versões variam de 1 a 40, possuindo capacidades e número de células diferentes. Cada versão possui 4 células a mais na vertical e na horizontal que a versão anterior, o que nos dá sempre capacidade de aramazenamento e tamanho crescentes. A figura \ref{figuraQRCodeVersao} nos mostra as primeiras e as últimas versões. 

\begin{figure}[h]
   \begin{center}
     \scalebox{0.8}{\includegraphics{imagens/qrcode-versao.png}}
   \end{center}
   \caption{Progressão das versões do QRCode.\label{figuraQRCodeVersao}}
\end{figure}

Uma tabela com todas as versões, diferentes níveis de correção de erro, e capacidades para os diferentes tipos de caracteres pode ser encontrada no apêndice \ref{qrcodeTabelaVersoes}.

\subsubsection{Utilização}

Como vimos, a utilização do QRCode vai depender de vários parâmetros, que vão determinar qual versão e nível de correção de erro vamos precisar. Dessa forma, é preciso que se determine os parâmetros a seguir, sempre tendo em mente a necessidade de armazenamento e o espaço disponível para a colocação do símbolo QRCode. A figura \ref{figuraQRCodeParametros} mostra como os fatores relacionados acima impactam no tamanho do símbolo.

\begin{figure}[h]
   \begin{center}
     \scalebox{0.8}{\includegraphics{imagens/qrcode-parametros.png}}
   \end{center}
   \caption{Parâmetros que determinam o tamanho final de um símbolo QRCode.\label{figuraQRCodeParametros}}
\end{figure}

\begin{itemize}
\item \textbf{Capacidade a ser armazenada} - Este fator é fundamental para a escolha da versão do QRCode e vai influenciar diretamente no tamanho do símbolo gerado. Geralmente não temos muita flexibilidade nesta escolha, pois será decorrente de outros fatores.
\item \textbf{Tipo de dados} - O tipo de dados vai influenciar na capacidade de armazenamento do símbolo. Caracteres númericos, por exemplo, podem ser codificados usando menos \textit{bits} que caracteres alfanuméricos, que por sua vez gastam menos \textit{bits} que \textit{bytes} completos. Devemos observar a forma mais vantajosa de representar a informação a ser codificada.
\item \textbf{Correção de erro} - Conforme dito anteriormente, as informações para correção de erro ocupam espaço no símbolo. Dessa forma, devemos determinar o nível de correção de erro suficiente para contornar eventuais falhas, mas que também não aumente mais do que podemos o tamanho do símbolo QRCode gerado.
\item \textbf{Resolução da impressora} - Este item impacta diretamente na área necessária para impressão do símbolo. Impressoras de baixa resolução vão precisar de mais espaço para representar cada célula com o número de pontos mínimo necessário.
\item \textbf{Resolução do leitor} -  De forma análoga a resolução da impressora, a resolução da câmera ou scanner que vai realizar a leitura do código QRCode influencia na área necessária para o registro do símbolo. Câmeras de baixa resolução vão limitar a versão do QRCode que pode ser utilizada por não conseguirem capturar todos os detalhes do símbolo necessários à leitura a partir de determinada versão.
\end{itemize}

Definidos todos esses parâmetros, pode ser então realizado o processo de codificação do símbolo. Durante esse processo, são ainda aplicados alguns filtros que têm como objetivo distribuir igualmente as células em preto e branco no código. Isso é feito para que sejam evitados problemas com contraste no momento da leitura, decorrentes de regiões com muito preto e outras regiões com muito branco.
